package dap;

public class sortieren {

    /**
     * Prueft ob ein Array im Breich [leftPos, rightPos] aufsteigend sortiert ist
     * @param array Das zu pruefende Array
     * @param leftPos Linke Grenze des zu pruefenden Bereichs
     * @param rightPos Rechte Grenze des zu pruefenden Bereichs
     * @return
     */
    public static boolean isSorted(int[] array, int leftPos, int rightPos) {

        assert leftPos >= 0 && rightPos < array.length && leftPos <= rightPos;

        if ( leftPos == rightPos) {
            return true;
        }
        for (int i = (leftPos + 1); i <= rightPos; i++) {
            if (array[i-1] > array[i]) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * Prueft ob ein Array aufsteigend sortiert ist
     * @param array Das zu pruefende Array
     * @return
     */
    public static boolean isSorted(int[] array) {

        assert array.length > 0 ;

        for (int i = 1; i < array.length; i++) {		// Durchlaufe array
            if (array[i-1] > array[i]) {				// Für alle außer dem ersten Element wird geprüft, 
                										// ob das vorherige größer als es selbst ist 
            	return false;							// Ist das der Fall, ist das Array nicht sortiert	
            }
        }
        return true;									// Sortiert, da nicht mit return false; vorzeitig abgebrochen wurde.
    }

    
    /**
     * Mergesort Algorithmus
     * @param array Ein Array voller Integer Zahlen.
     */
    public static void mergeSort( int[] array ) {
        int[] tmpArray = new int[ array.length ];
        mergeSort( array, tmpArray, 0, array.length - 1 );

        assert isSorted(array);
    }

    /**
     * Hilfsfunktion, welche die rekursiven Aufrufe ausfuehrt
     * @param a ein zu sortierendes Array mit Integer Zahlen
     * @param tmpArray ein hilfs-array
     * @param left die linke Grenze des Teilarrays
     * @param right die rechte Grenze des Teilarrays
     */
    private static void mergeSort( int[] a, int[] tmpArray, int left, int right ) {

        assert a.length > 0 && left <= right && left >= 0 && right < a.length && tmpArray.length == a.length;

        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center ); //linkes Teilarray
            mergeSort( a, tmpArray, center + 1, right ); //rechtes Teilarray
            merge( a, tmpArray, left, center + 1, right ); //beide Teilarrays verschmelzen
        }
    }

    /**
     * Hilfsfunktion, welche zwei sortierte Teilarrays verschmilzt
     * @param a Ein Array voller Integer Zahlen
     * @param tmpArray ein hilfs-array
     * @param leftPos die linke Grenze des ersten Teilarrays
     * @param rightPos die rechte grenze des 1. und  linke Grenze des 2. Teilarrays
     * @param rightEnd die rechte Grenze des zweiten Teilarrays
     */
    private static void merge( int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int leftStart = tmpPos;
        int numElements = rightEnd - leftPos + 1;

        assert leftEnd <= rightEnd && leftPos <= rightEnd && leftStart >= 0 && a.length > 0 && rightEnd < a.length;

        //Zahlen in tmpArray einsortieren
        while( leftPos <= leftEnd && rightPos <= rightEnd ) {
            if( a[ leftPos ] <= a[ rightPos ] ) {
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            } else {
                tmpArray[ tmpPos++ ] = a[ rightPos++ ];
            }

            assert isSorted(tmpArray, leftStart, tmpPos-1) : "Nicht sortiert in ["+leftStart+","+(tmpPos-1)+"]";
        }

        // den Rest der ersten haelfte kopieren
        while( leftPos <= leftEnd ) {

            if (leftPos < leftEnd) {
                assert tmpArray[leftPos] <= tmpArray[leftPos+1] ;
            }

            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        }

        // den rest der zweiten haelfte kopieren
        while( rightPos <= rightEnd ) {

            if (rightPos < rightEnd) {
                assert tmpArray[rightPos] <= tmpArray[rightPos+1] ;
            }

            tmpArray[ tmpPos++ ] = a[ rightPos++ ];
        }

        // tmpArray zurueck kopieren
        for( int i = 0; i < numElements; i++, rightEnd-- ) {
            a[ rightEnd ] = tmpArray[ rightEnd ];
        }
    }    

    /**
     * Sortiert das Array mit Bubblesort
     * @param array Das Array, das sortiert werden soll
     */  
	public static void bubbleSort(int[] array) {
		boolean bChanged = true;

		while (bChanged) {
			bChanged = false;
			for (int i = 0; i < array.length - 1; i++) {
				if (array[i] > array[i + 1]) {
					int iTemp = array[i];
					array[i] = array[i + 1];
					array[i + 1] = iTemp;
					bChanged = true;
				}
			}
		}
	}
  
    /**
     * Sortiert das Array mit Quicksort
     * @param array Das Array, das sortiert werden soll
     */  
    public static void quicksort(int[] array) {
        quicksort(array, 0, array.length-1);
    }
  
    /**
     * Sortiert das Array mit Quicksort
     * @param array Das Array, das sortiert werden soll
     * @param l linke Grenze
     * @param r rechte Grenze
     */
	private static void quicksort (int[] array, int l, int r) {
		if (l < r) { // mehr als ein Element zu sortieren
			int i = l, j = r, tmp;
			int pivot = array[(l+r)/2];  // Pivotelement
			while (i <= j) {    // Initialisierug: i = l, j = r
	                	        // Invariante: Elemente array[l..i-1] <= pivot, Elemente array[j+1..r] >= pivot
				while (array[i] < pivot) {      // Initialisierung: i = l, array[l..i-1] mit pivot verglichen
					i++;                    // Invariante: array[i] < pivot, Elemente aus array[l..i-1] < pivot
				}                               // Austritt: array[i] >= pivot
				assert array[i] >= pivot : "quickSort - array[i] < pivot!";
				while (array[j] > pivot) {      // Initialisierung: j = r, array[j+1..r] mit pivot verglichen
					j--;                    // Invariante: array[j] > pivot, Elemente aus array[j+1..r] > pivot
				}                               // Austritt: array[j] <= pivot
				assert array[j] <= pivot : "quicksort - array[j] > pivot!";
				if (i <= j) {
					tmp = array[i];
					array[i] = array[j];
					array[j] = tmp;
					i++;
					j--;
				}
				assert array[i-1] <= pivot : "quickSort - array[i-1] > pivot!";
				assert array[j+1] >= pivot : "quickort - array[j+1] < pivot!";
			}                   // Austritt: i > j, Elemente array[l..i] <= pivot, Elemente array[j..r] >= pivot
			
			// rekursive Aufrufe
			quicksort(array, l, j);
			quicksort(array, i, r);
		}
	}

}
